package lesson8;

import java.util.Arrays;

public class SortingAlgorithms {

		public static void main(String[] args) {
			
			int[] x = {7,3,6};
			
			
			long ts = System.currentTimeMillis();
			//System.out.println(Arrays.toString(bubbleSort(x)));
			//System.out.println(Arrays.toString(selectionSort(x)));
			//selectionSort(x);
			//System.out.println(System.currentTimeMillis()-ts);
			System.out.println(Arrays.toString(countingSort(x, 9)));
		}
		
		public static int[] bubbleSort(int[] array)
		{
			for(int j = 0; j < array.length; j++)
			{
				boolean sorted = true;
				for(int i = 1; i < array.length-j; i++)
				{
					if(array[i-1] > array[i])
					{
						//swap
						int temp = array[i-1];
						array[i-1] = array[i];
						array[i] = temp;
						sorted = false;
					}
				}
				if(sorted)
					break;
			}
			return array;
		}

		
		//could not work with optimization, find out what to do for homework!
		public static int[] selectionSort(int[] array)
		{
			for(int i = 0; i < array.length; i++)
			{
				int minIndex = i;
				int maxIndex = i;
				for(int j = i+1; j < array.length; j++)
				{
					if(array[j] < array[minIndex])
					{
						minIndex = j;
					}
					if(array[j] > array[maxIndex])
					{
						maxIndex = j;
					}
				}
				
				//swap min with first and max with last
				int temp = array[minIndex];
				array[minIndex] = array[i];
				array[i] = temp;
				
				int temp1 = array[maxIndex];
				array[maxIndex] = array[array.length-i-1];
				array[array.length-i-1] = temp1;
				
				if(i == array.length/2)
					break;
			}
			return array;
		}
		
		public static int[] countingSort(int[] array, int maxValue)
		{
			int[] results = new int[array.length];
			
			int[] helper = new int[maxValue+1];
			
			for(int i = 0; i < array.length; i++)
			{
				helper[array[i]]++;
			}
			
			int resultIndex = 0;
			for(int i = 0; i < helper.length; i++)
			{
				for(int j = 0; j < helper[i]; j++)
				{
					results[resultIndex] = i;
					resultIndex++;
				}
			}
			
			return results;
		}
}
